#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(): val(0), next(nullptr) {};
    ListNode(int x): val(x), next(nullptr) {};
};

void printListNode(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        cout << current->val << " ";
        current = current->next;
    }
}

// 快慢指针删除倒数第n个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* befordHead = new ListNode();
    befordHead->next = head;
    
    ListNode *fast = befordHead, *slow = befordHead;
    // 快指针移动到和慢指针相差n个
    // 保证fast不为null才能访问它的next
    while (n-- && fast != nullptr) {
        fast = fast->next;
    }
    // 遍历fast的下一个为null停止
    while (fast->next != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* temp = slow->next;
    slow->next = slow->next->next;
    delete temp;
    temp = nullptr;
    return befordHead->next;
}

int main() {
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(6);
    ListNode* node4 = new ListNode(3);
    ListNode* node5 = new ListNode(4);
    ListNode* node6 = new ListNode(5);
    ListNode* node7 = new ListNode(6);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
    node6->next = node7;

    cout << "origin: " << "\n";
    printListNode(node1);

    node1 = removeNthFromEnd(node1, 7);

    cout << "after: " << "\n";
    printListNode(node1);
    return 0;
}